#coding=utf-8
class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        #dp[i][j]表示s1[:i]和s2[:j]是否能构成s3[:i+j]
        len1 = len(s1)
        len2 = len(s2)
        len3 = len(s3)
        if len1 + len2 != len3:
            return False
        dp = [[False for j in range(len2+1)] for i in range(len1+1)]

        print 0, 0, dp[0][0]
        for j in range(1, len2+1):
            if s2[j-1] == s3[j-1] and dp[0][j-1]:
                dp[0][j] = True
        
        for i in range(1, len1+1):
            if s1[i-1] == s3[i-1] and dp[i-1][0]:
                dp[i][0] = True
        
        for i in range(1, len1+1):
            for j in range(1, len2+1):
                if (s2[j-1] == s3[i+j-1] and dp[i][j-1]) or (s1[i-1] == s3[i+j-1] and dp[i-1][j]):
                    dp[i][j] = True
        return dp[len1][len2]
